package com.leetcode.hot100;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-24  21:15
 * @Description: TODO
 * @Version: 1.0
 */
public class 零钱兑换 {
    public static void main(String[] args) {
        int[] coins = {1};
        int amount = 0;
        System.out.println(coinChange(coins, amount));
    }

    public static int coinChange(int[] coins, int amount) {
        int[][] ints = new int[coins.length + 1][amount + 1];
        for (int i = 1; i <= coins.length; i++) {
            ints[i][0] = 0;
            for (int j = 1; j <= amount; j++) {
                ints[0][j] = amount + 1;
                if (j >= coins[i - 1]) {
                    int init = ints[i - 1][j];
                    int end = ints[i][j - coins[i - 1]];
                    ints[i][j] = Math.min(init, end + 1);
                } else {
                    ints[i][j] = ints[i - 1][j];
                }
            }
        }
        return ints[coins.length][amount] == amount + 1 ? -1 : ints[coins.length][amount];
    }


    class Solution {
        public int coinChange(int[] coins, int amount) {
            // dp[i][j] 表示前 i 种***，恰价值为 j，所需要的最小数目
            int N = coins.length;
            int[][] dp = new int[2][amount + 1];
            // initialize dp[i][0] = 0, dp[0][j] = amount + 1(j >= 1); 设为 amount + 1 表示该值不可能
            for (int j = 1; j <= amount; j++) dp[0][j] = amount + 1;
            // dp[i][j] = min{dp[i - 1][j], dp[i][j - coins[i - 1]] + 1}
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= amount; j++) {
                    if (j - coins[i - 1] >= 0) {
                        dp[i & 1][j] = Math.min(dp[(i - 1) & 1][j], dp[i & 1][j - coins[i - 1]] + 1);
                    } else {
                        dp[i & 1][j] = dp[(i - 1) & 1][j];
                    }
                }
            }
            // dp[coins.length][amount]
            return dp[N & 1][amount] == amount + 1 ? -1 : dp[N & 1][amount];
        }
    }
}
